#include "recursion/reverse_list.h"

#include <iostream>

ListNode* reverseList(ListNode* head)
{
    if (nullptr == head || nullptr == head->next)
        return head;
    ListNode* newHead = reverseList(head->next);
    // 哨兵节点后的第一个节点指向哨兵
    head->next->next = head;
    // 哨兵节点后置空，成为链表最后一个节点
    head->next = nullptr;
    return newHead;
}

static void reversePrintList(const ListNode* head)
{
    if (nullptr == head)
        return;
    std::cout << head->data << std::endl;
    reversePrintList(head->next);
}

void testListForRecursion()
{
    std::cout << "================= enter into testListForRecursion =================" << std::endl;
    ListNode* head = new ListNode(0);
    ListNode* node1 = new ListNode(1);
    ListNode* node2 = new ListNode(2);
    ListNode* node3 = new ListNode(3);

    head->next = node1;
    node1->next = node2;
    node2->next = node3;

    node3->next = nullptr;

    printList(head);

    ListNode* newHead = reverseList(head);

    reversePrintList(newHead);

    deleteList(newHead);

    std::cout << "================= levae testListForRecursion =================" << std::endl;
}